package fun.ticsmyc.dataStructure;

import fun.ticsmyc.tools.ListNode;

public class 链表排序 {

    //快排思路转换为链表 （会超时  最坏情况退化成n^2）
    public ListNode sortList(ListNode head) {

        if(head == null || head.next == null){
            return head;
        }

        ListNode tail = head;
        while(tail.next != null){
            tail = tail.next;
        }
        return sortList(head,tail)[0];
    }
    public ListNode[] sortList(ListNode head,ListNode tail) {
        if(head == tail){
            return new ListNode[]{head,tail};
        }



        ListNode[] partation = partation(head, tail);

        ListNode resHead = partation[2];
        ListNode resTail =  partation[3];

        if(partation[0]!=null){
            ListNode[] lRes = sortList(partation[0],partation[1]);
            lRes[1].next = partation[2];
            resHead = lRes[0];
        }
        if(partation[4]!=null){
            ListNode[] rRes = sortList(partation[4],partation[5]);
            partation[3].next = rRes[0];
            resTail = rRes[1];
        }
        return new ListNode[]{resHead,resTail};
    }

    /**
     * lhead  ltail  mhead mtail rhead rtail
     */
    private ListNode[] partation(ListNode head, ListNode tail) {
        ListNode lHead =new ListNode(-1);
        ListNode lCur = lHead;
        ListNode rHead =new ListNode(-1);
        ListNode rCur = rHead;
        ListNode mHead =head;
        ListNode mCur = mHead;

        head = head.next;
        while(head != tail.next){
            if(head.val <mHead.val){
                lCur.next = head;
                lCur  = lCur.next;
            }else if(head.val > mHead.val){
                rCur.next = head;
                rCur=rCur.next;
            }else{
                mCur.next = head;
                mCur = mCur.next;
            }
            head = head.next;
        }
        lCur.next = null;
        mCur.next = null;
        rCur.next = null;
        return new ListNode[]{lHead.next,lCur,mHead,mCur,rHead.next,rCur};
    }

}
